def quick_sort(array, left, right):
  if left >= right:
    return
  start, end = left, right
  flag = array[left]
  while left < right:
    print('left={}, right={}'.format(left, right))
    while left < right and array[right] >= flag:
      right = right - 1
    if array[right] < flag:
      array[left], array[right] = array[right], array[left]
    while left < right and array[left] <= flag:
      left = left + 1
    if array[left] > flag:
      array[left], array[right] = array[right], array[left]
  quick_sort(array, start, left - 1)
  quick_sort(array, left + 1, end)


if __name__ == '__main__':
  array = [1, 1, 4, 5, 1, 4]
  start, end = 0, len(array) - 1
  quick_sort(array, start, end)
  print(array)
